class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        stack = []
        for i in range(len(expression)):
            i = (i + 1) * (-1)
            c = expression[i]
            if c in ")ft":
                stack.append(c)
            elif c == '(':
                pass # d丢掉
            elif c == '!':
                stack.append(self.cnot(stack))
            elif c == '&':
                stack.append(self.cand(stack))
            elif c == '|':
                stack.append(self.cor(stack))
        return stack.pop() == 't'

    def cnot(self, stack):
        b = stack.pop()
        stack.pop() # )
        return 'f' if b == 't' else 't'

    def cand(self, stack):
        v = stack.pop()
        hasf = False
        while v != ')':
            if not hasf:
                if v == 'f':
                    hasf = True
            v = stack.pop()

        return 'f' if hasf else 't'

    def cor(self, stack):
        v = stack.pop()
        hast = False
        while v != ')':
            if not hast:
                if v == 't':
                    hast = True
            v = stack.pop()
        return 't' if hast else 'f'

solu = Solution()
print(solu.parseBoolExpr("|(f,t)"))